package third

import "strconv"

/*
	给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。
	一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

	示例 1:

	输入: 12258
	输出: 5
	解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
	提示：

	0 <= num < 231

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func TranslateNum(num int) int {
	return translateNum(num)
}

/*
	f(i-1)表示前i-1个数的组合数量
	对于i来说有如下可能
	nums[i-1]=1:f(i)=f(i-1)+f(i-2)
	nums[i-1]=2:nums[i]
*/
func translateNum(num int) int {
	s := strconv.Itoa(num)
	dp := make([]int, len(s))
	dp[0] = 1
	for i := 1; i < len(s); i++ {
		if s[i-1] == '1' {
			if i >= 2 {
				dp[i] = dp[i-1] + dp[i-2]
			} else {
				dp[i] = dp[i-1] + 1
			}
		} else if s[i-1] == '2' {
			if s[i] > '5' {
				dp[i] = dp[i-1]
			} else {
				if i < 2 {
					dp[i] = dp[i-1] + 1
					continue
				}
				dp[i] = dp[i-1] + dp[i-2]
			}
		} else {
			dp[i] = dp[i-1]
		}
	}
	return dp[len(dp)-1]
}
